package ljl.alg.wangzheng_camp.round1.bfsdfs;

import java.util.LinkedList;

/**
 * 哦！
 *
 * 1. 路飞说在题目给定限制条件，0,100 下，有个地推公式
 * 2. 官方题解说，随着 k 增大，画了一下格子的值变化趋势，只需要考虑右和下
 *
 * 这两个骚套路很难推出来
 * 除非有人说：有特殊递推公式，必须用；或你看看能不能只考虑右和下，否则一般人谁能发现？
 *
 * 先不考虑这两个优化吧
 *
 * 不难，但是不能那么流畅的写出来
 *
 * */
public class _interview13_robot_moving_area {
    
    /*
     * dp
     * 写了一半，不会写了
     * */
    public int movingCount(int m, int n, int k) {
        boolean[][] visitable = new boolean[m][n];
        visitable[0][0] = true;
        int sum = 0;
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (check(i, j, k, visitable)) {
                    visitable[i][j] = true;
                    sum++;
                }
            }
        }
        return sum;
    }
    boolean check(int i, int j, int t, boolean[][] visitable) {
        if (visitable[i][j]
            || i > 0 && visitable[i - 1][j]
            || j > 0 && visitable[i][j - 1]
            || i < visitable.length - 1 && visitable[i + 1][j]
            || j < visitable[0].length - 1 && visitable[i][j + 1]
        ) return mySum(i) + mySum(j) <= t;
        return false;
    }
    int mySum(int i) {
        int res = 0;
        while (i > 0) {
            res += i % 10;
            i /= 10;
        }
        return res;
    }
    
    /*
    * bfs
    * 优化后只用考虑两个方向，我不考虑优化解
    * */
    public int movingCount2(int m, int n, int k) {
        boolean[][] visited = new boolean[m][n];
        int[][] dirs = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
        LinkedList<int[]> q = new LinkedList<>();
        q.offer(new int[]{0, 0});
        visited[0][0] = true;
        int res = 1;
        while (!q.isEmpty()) {
            int[] pos = q.poll();
            int x = pos[0], y = pos[1];
            for (int[] dir : dirs) {
                int newX = x + dir[0], newY = y + dir[1];
                if (ojbk(visited, m, n, newX, newY, k)) {
                    res++;
                    visited[newX][newY] = true;
                    q.offer(new int[] {newX, newY});
                }
            }
        }
        return res;
    }
    boolean ojbk(boolean[][] visited, int m, int n, int x, int y, int t) {
        if (x < 0 || y < 0 || x >= m || y >= n || visited[x][y]) return false;
        return ss(x) + ss(y) <= t;
    }
    int ss(int i) {
        int res = 0;
        while (i > 0) {
            res += i % 10;
            i /= 10;
        }
        return res;
    }
}
